home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / listings / v_12_02 / gage / compress.c < prev    next >
C/C++ Source or Header  |  1993-11-12  |  5KB  |  204 lines
  1. /* compress.c */
  2.  
  3. #include <stdio.h>
  4.  
  5. #define BLOCKSIZE 5000   /* Maximum block size */
  6. #define HASHSIZE  4096   /* Size of hash table */
  7. #define MAXCHARS   200   /* Char set per block */
  8.  
  9. unsigned char buffer[BLOCKSIZE]; /* Data block */
  10. unsigned char leftcode[256];     /* Pair table */
  11. unsigned char rightcode[256];    /* Pair table */
  12. unsigned char left[HASHSIZE];    /* Hash table */
  13. unsigned char right[HASHSIZE];   /* Hash table */
  14. unsigned char count[HASHSIZE];   /* Pair count */
  15. int size;        /* Size of current data block */
  16.  
  17. /* Function prototypes */
  18. int lookup (unsigned char, unsigned char);
  19. int fileread (FILE *);
  20. void filewrite (FILE *);
  21. void compress (FILE *, FILE *);
  22.  
  23. /* Return index of character pair in hash table */
  24. /* Deleted nodes have count of 1 for hashing */
  25. int lookup (unsigned char a, unsigned char b)
  26. {
  27.   int index;
  28.  
  29.   /* Compute hash key from both characters */
  30.   index = (a ^ (b << 5)) & (HASHSIZE-1);
  31.  
  32.   /* Search for pair or first empty slot */
  33.   while ((left[index] != a || right[index] != b) &&
  34.          count[index] != 0)
  35.     index = (index + 1) & (HASHSIZE-1);
  36.  
  37.   /* Store pair in table */
  38.   left[index] = a;
  39.   right[index] = b;
  40.   return index;
  41. }
  42.  
  43. /* Read next block from input file into buffer */
  44. int fileread (FILE *input)
  45. {
  46.   int c, index, used=0;
  47.  
  48.   /* Reset hash table and pair table */
  49.   for (c = 0; c < HASHSIZE; c++)
  50.     count[c] = 0;
  51.   for (c = 0; c < 256; c++) {
  52.     leftcode[c] = c;
  53.     rightcode[c] = 0;
  54.   }
  55.   size = 0;
  56.  
  57.   /* Read data until full or few unused chars */
  58.   while (size < BLOCKSIZE && used < MAXCHARS &&
  59.          (c = getc(input)) != EOF) {
  60.     if (size > 0) {
  61.       index = lookup(buffer[size-1],c);
  62.       if (count[index] < 255) ++count[index];
  63.     }
  64.     buffer[size++] = c;
  65.  
  66.     /* Use rightcode to flag data chars found */
  67.     if (!rightcode[c]) {
  68.       rightcode[c] = 1;
  69.       used++;
  70.     }
  71.   }
  72.   return c == EOF;
  73. }
  74.  
  75. /* Write each pair table and data block to output */
  76. void filewrite (FILE *output)
  77. {
  78.   int i, len, c = 0;
  79.  
  80.   /* For each character 0..255 */
  81.   while (c < 256) {
  82.  
  83.     /* If not a pair code, count run of literals */
  84.     if (c == leftcode[c]) {
  85.       len = 1; c++;
  86.       while (len<127 && c<256 && c==leftcode[c]) {
  87.         len++; c++;
  88.       }
  89.       putc(len + 127,output); len = 0;
  90.       if (c == 256) break;
  91.     }
  92.  
  93.     /* Else count run of pair codes */
  94.     else {
  95.       len = 0; c++;
  96.       while (len<127 && c<256 && c!=leftcode[c] || 
  97.           len<125 && c<254 && c+1!=leftcode[c+1]) {
  98.         len++; c++;
  99.       }
  100.       putc(len,output);
  101.       c -= len + 1;
  102.     }
  103.  
  104.     /* Write range of pairs to output */
  105.     for (i = 0; i <= len; i++) {
  106.       putc(leftcode[c],output);
  107.       if (c != leftcode[c])
  108.         putc(rightcode[c],output);
  109.       c++;
  110.     }
  111.   }
  112.  
  113.   /* Write size bytes and compressed data block */
  114.   putc(size/256,output);
  115.   putc(size%256,output);
  116.   fwrite(buffer,size,1,output);
  117. }
  118.  
  119. /* Compress from input file to output file */
  120. void compress (FILE *infile, FILE *outfile)
  121. {
  122.   int leftch, rightch, code, oldsize;
  123.   int index, r, w, best, done = 0;
  124.  
  125.   /* Compress each data block until end of file */
  126.   while (!done) {
  127.     done = fileread(infile);
  128.     code = 256;
  129.  
  130.     /* Compress this block */
  131.     for (;;) {
  132.  
  133.       /* Get next unused char for pair code */
  134.       for (code--; code >= 0; code--)
  135.         if (code==leftcode[code] && !rightcode[code])
  136.           break;
  137.  
  138.       /* Must quit if no unused chars left */
  139.       if (code < 0) break;
  140.  
  141.       /* Find most frequent pair of chars */
  142.       for (best=2, index=0; index<HASHSIZE; index++)
  143.         if (count[index] > best) {
  144.           best = count[index];
  145.           leftch = left[index];
  146.           rightch = right[index];
  147.         }
  148.  
  149.       /* Done if no more compression possible */
  150.       if (best < 3) break;
  151.  
  152.       /* Replace pairs in data, adjust pair counts */
  153.       oldsize = size - 1;
  154.       for (w = 0, r = 0; r < oldsize; r++) {
  155.         if (buffer[r] == leftch &&
  156.             buffer[r+1] == rightch) {
  157.           if (r > 0) {
  158.             index = lookup(buffer[w-1],leftch);
  159.             if (count[index] > 1) --count[index];
  160.             index = lookup(buffer[w-1],code);
  161.             if (count[index] < 255) ++count[index];
  162.           }
  163.           if (r < oldsize - 1) {
  164.             index = lookup(rightch,buffer[r+2]);
  165.             if (count[index] > 1) --count[index];
  166.             index = lookup(code,buffer[r+2]);
  167.             if (count[index] < 255) ++count[index];
  168.           }
  169.           buffer[w++] = code;
  170.           r++; size--;
  171.         }
  172.         else buffer[w++] = buffer[r];
  173.       }
  174.       buffer[w] = buffer[r];
  175.  
  176.       /* Add to pair substitution table */
  177.       leftcode[code] = leftch;
  178.       rightcode[code] = rightch;
  179.  
  180.       /* Delete pair from hash table */
  181.      index = lookup(leftch,rightch);
  182.      count[index] = 1;
  183.     }
  184.     filewrite(outfile);
  185.   }
  186. }
  187.  
  188. void main (int argc, char *argv[])
  189. {
  190.   FILE *infile, *outfile;
  191.  
  192.   if (argc != 3)
  193.     printf("Usage: compress infile outfile\n");
  194.   else if ((infile=fopen(argv[1],"rb"))==NULL)
  195.     printf("Error opening input %s\n",argv[1]);
  196.   else if ((outfile=fopen(argv[2],"wb"))==NULL)
  197.     printf("Error opening output %s\n",argv[2]);
  198.   else {
  199.     compress(infile,outfile);
  200.     fclose(outfile);
  201.     fclose(infile);
  202.   }
  203. }
  204.